namespace LeetCode1743RestoreArray {

    /**
     * 存在一个由 n 个 不同元素 组成的整数数组 nums
     * nums.length == n
     * adjacentPairs.length == n - 1
     * adjacentPairs[i].length == 2
     * 2 <= n <= 105
     * -105 <= nums[i], ui, vi <= 105
     * 题目数据保证存在一些以 adjacentPairs 作为元素对的数组 nums
     * 
     */

    function restoreArray(adjacentPairs: number[][]): number[] {
        let ans = [];
        let map: Map<number, number[]> = new Map();
        // 掃描二維數組，建立MAP
        for (const [p, q] of adjacentPairs) {
            if (map.get(p) == undefined)
                map.set(p, [q]);
            else
                map.get(p)?.push(q);

            if (map.get(q) == undefined)
                map.set(q, [p]);
            else
                map.get(q)?.push(p);
        }
        // find first single data
        for (const [e, adj] of map.entries()) {
            if (adj.length === 1) {
                ans[0] = e;
                ans[1] = adj[0];
                break;
            }
        }
        // 數據處理
        for (let i = 2; i <= adjacentPairs.length; i++) {
            const adj: number[] = map.get(ans[i - 1]) || [];
            ans[i] = ans[i - 2] == adj[0] ? adj[1] : adj[0];
        }
        return ans;
    };

}